
import java.util.Arrays;


public class QuickSortTest {

    public static void main(String[] args) {
        int[] array = {-4, 2, 10, 9, 8, 7, 6};
        System.out.println("before sort = " + Arrays.toString(array));
        arraySort(array);
        System.out.println("after sort = " + Arrays.toString(array));
        System.out.println("The third smallest one is " + array[2]);
    }


    private static void arraySort(int[] array){
        quickSort(array, 0, array.length -1);
    }

    /**
     * 快速排序
     * @param array int数组
     * @param startIndex 待排序元素起始位置下标
     * @param endIndex 待排序元素终止位置下标
     */
    private static void quickSort(int[] array, int startIndex, int endIndex){
        if (startIndex >= endIndex) {
            return;
        }

        int pivotIndex = partition(array, startIndex, endIndex);
        quickSort(array, startIndex, pivotIndex - 1);
        quickSort(array, pivotIndex+ 1, endIndex);
    }

    /**
     * 分割数组
     * @param array int数组
     * @param startIndex 待排序元素起始位置下标
     * @param endIndex 待排序元素终止位置下标
     * @return 分割点下标
     */
    private static int partition(int[] array, int startIndex, int endIndex){
        //区间最后一个元素作为分割点
        int pivot = array[endIndex];
        int i = startIndex;
        for (int j = startIndex; j < endIndex; j++){
            if (array[j] < pivot){
                swap(array, i, j);
                i++;
            }
        }
        swap(array, i, endIndex);
        return i;
    }

    /**
     * 交换数组中两个元素
     */
    private static void swap(int[] array, int i, int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

}


